{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Good Meals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #大餐计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>大餐</strong> 是指 <strong>恰好包含两道不同餐品</strong> 的一餐，其美味程度之和等于 2 的幂。</p>\n",
    "\n",
    "<p>你可以搭配 <strong>任意</strong> 两道餐品做一顿大餐。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>deliciousness</code> ，其中 <code>deliciousness[i]</code> 是第 <code>i<sup>​​​​​​</sup>​​​​</code>​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 <strong>大餐</strong> 的数量。结果需要对 <code>10<sup>9</sup> + 7</code> 取余。</p>\n",
    "\n",
    "<p>注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>deliciousness = [1,3,5,7,9]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。\n",
    "它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>deliciousness = [1,1,1,3,3,3,7]\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= deliciousness.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= deliciousness[i] <= 2<sup>20</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-good-meals](https://leetcode.cn/problems/count-good-meals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-good-meals](https://leetcode.cn/problems/count-good-meals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,7,9]', '[1,1,1,3,3,3,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return int(lt*(lt-1)/2)\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1)/2)+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            #sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1)/2)\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return int(rs)\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        factor = []\n",
    "        p = 1 \n",
    "        while p * p <= k:\n",
    "            if k % p == 0:\n",
    "                factor.append(p)\n",
    "                if p * p < k:\n",
    "                    factor.append(k // p)\n",
    "            p += 1\n",
    "        dic = collections.Counter()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += dic[k // gcd(k, num)]\n",
    "            for f in factor:\n",
    "                if num % f == 0:\n",
    "                    dic[f] += 1 \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []\n",
    "        d = 1\n",
    "        while d * d <= k:\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        #  (x1 * x2 ) % k == 0\n",
    "        #  一眼 gcd 好吧\n",
    "        choices = [i for i in range(1, k+1) if k% i == 0]\n",
    "        \n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        m = defaultdict(int)\n",
    "        for x in nums:\n",
    "            v = gcd(x, k)\n",
    "            ans += m[k // v]\n",
    "            for c in choices:\n",
    "                if x % c == 0:\n",
    "                    m[c] += 1\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs0(self, nums: List[int], k: int) -> int:\n",
    "        nm=len(nums)\n",
    "        tot=0\n",
    "        for i in range(nm-1):\n",
    "            for j in range(i+1,nm):\n",
    "                if nums[i]*nums[j]%k==0: tot+=1\n",
    "        return tot\n",
    "\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        ans = 0\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    ans += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "            if num * num % k == 0:\n",
    "                ans -= 1\n",
    "\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return (lt*(lt-1))//2\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1))//2+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            #sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1))//2\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return rs\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        factor = []\n",
    "        p = 1 \n",
    "        while p * p <= k:\n",
    "            if k % p == 0:\n",
    "                factor.append(p)\n",
    "                if p * p < k:\n",
    "                    factor.append(k // p)\n",
    "            p += 1\n",
    "        dic = collections.Counter()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += dic[k // gcd(k, num)]\n",
    "            for f in factor:\n",
    "                if num % f == 0:\n",
    "                    dic[f] += 1 \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnts, ans = Counter(), 0\n",
    "        for num in nums:\n",
    "            g = gcd(num, k)\n",
    "            for c in cnts:\n",
    "                if not (c * g) % k:\n",
    "                    ans += cnts[c]\n",
    "            cnts[g] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return (lt*(lt-1))//2\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1))//2+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            #sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1))//2\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return rs\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    res += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "\n",
    "            if num * num % k == 0:\n",
    "                res -= 1\n",
    "        \n",
    "        return res // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        d=Counter()\n",
    "        for v in nums:\n",
    "            d[gcd(v,k)]+=1\n",
    "        \n",
    "        res=0\n",
    "        for k1,v1 in d.items():\n",
    "            for k2,v2 in d.items():\n",
    "                if k1*k2%k==0:\n",
    "                    if k1==k2:\n",
    "                        res+=v1*(v1-1)\n",
    "                    else:\n",
    "                        res+=v1*v2\n",
    "        return res//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnts, ans = Counter(), 0\n",
    "        for num in nums:\n",
    "            g = gcd(num, k)\n",
    "            for c in cnts:\n",
    "                if (c * g) % k==0:\n",
    "                    ans += cnts[c]\n",
    "            cnts[g] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        ans = 0\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    ans += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "            if num * num % k == 0:\n",
    "                ans -= 1\n",
    "\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    res += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "\n",
    "            if num * num % k == 0:\n",
    "                res -= 1\n",
    "        \n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            cnt[gcd(v,k)] += 1\n",
    "        ans = 0\n",
    "\n",
    "        for a,b in cnt.items():\n",
    "            for c,d in cnt.items():\n",
    "                if a * c % k == 0: \n",
    "                    ans += b * d\n",
    "        for num in nums:\n",
    "            if num * num % k == 0:\n",
    "                ans -= 1\n",
    "        return ans // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter(gcd(n, k) for n in nums)\n",
    "        res = sum(c[g1]*c[g2] for g1, g2 in combinations(c.keys(), 2) if g1*g2 % k == 0)\n",
    "        res += sum(n*(n-1)//2 for g, n in c.items() if g * g % k == 0)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []  \n",
    "        d = 1\n",
    "        while d * d <= k:  # 预处理 k 的所有因子\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []  \n",
    "        d = 1\n",
    "        while d * d <= k:  # 预处理 k 的所有因子\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return int(lt*(lt-1)/2)\n",
    "        kk=0\n",
    "        k1=0\n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            if ki==1:\n",
    "                k1+=1\n",
    "                continue\n",
    "            else :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1))/2+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1))/2\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return int(rs)\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return int(lt*(lt-1)/2)\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1)/2)+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1)/2)\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return int(rs)\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        f = []\n",
    "        d = 1\n",
    "        while d * d <= k:\n",
    "            if k % d == 0:\n",
    "                f.append(d)\n",
    "                if d * d < k:\n",
    "                    f.append(k // d)\n",
    "            d += 1\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans += cnt[k//gcd(k, x)]\n",
    "            for d in f:\n",
    "                if x % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []  \n",
    "        d = 1\n",
    "        while d * d <= k:  # 预处理 k 的所有因子\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k // gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = 10 ** 5\n",
    "        prime = []\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            if a < b:\n",
    "                a, b = b, a\n",
    "            return gcd(b, a % b)\n",
    "\n",
    "        flag = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            if flag[i] == 0:\n",
    "                prime.append(i)\n",
    "            j = 0\n",
    "            while prime[j] * i <= n:\n",
    "                flag[prime[j] * i] = 1\n",
    "                if i % prime[j] == 0:\n",
    "                    break\n",
    "                j += 1\n",
    "        stack = [0] * 1000\n",
    "        stack[0] = 1\n",
    "        counter = [0] * (n + 1)\n",
    "        ret = 0\n",
    "        for x in nums:\n",
    "            i = 0\n",
    "            sright = 1\n",
    "            \n",
    "            g = k // gcd(k, x)\n",
    "            ret += counter[g]\n",
    "            counter[1] += 1\n",
    "            while prime[i] * prime[i] <= x:\n",
    "                p = 1\n",
    "                tmp = sright\n",
    "                while x % prime[i] == 0:\n",
    "                    x //= prime[i]\n",
    "                    p *= prime[i]\n",
    "                    for j in range(tmp):\n",
    "                        stack[sright] = t = p * stack[j]\n",
    "                        counter[t] += 1\n",
    "                        sright += 1\n",
    "                i += 1\n",
    "            if x != 1:\n",
    "                for j in range(sright):\n",
    "                    counter[stack[j] * x] += 1\n",
    "            # print(g, counter[:8], ret)\n",
    "        return ret     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "pt=PrimeTable(10**5+5)\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        cnt=Counter()\n",
    "        for x in nums:\n",
    "            res+=cnt[k//gcd(k,x)]\n",
    "            for i in pt.get_factors(x):\n",
    "                cnt[i]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个数的所有因子，时间复杂度 O(MlogM)\n",
    "M = 100001\n",
    "divisors = [[] for _ in range(M)]\n",
    "for i in range(1, M):\n",
    "    for j in range(i, M, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += cnt[k // gcd(num, k)]\n",
    "            for x in divisors[num]:\n",
    "                cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):  # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors[v]:\n",
    "                cnt[d] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1,MX):\n",
    "    for j in range(i,MX,i):\n",
    "        divisors[j].append(i)\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for num in nums:\n",
    "            ans += cnt[k/gcd(num,k)]\n",
    "            for d in divisors[num]:\n",
    "                cnt[d]+=1\n",
    "            # print(k/gcd(num,k),cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):  # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x in nums:\n",
    "            ans += cnt[k // gcd(x, k)]\n",
    "            for i in divisors[x]:\n",
    "                cnt[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "数学\n",
    "nums[i] * nums[j] % k === 0\n",
    "固定nums[j], 统计nums[i]\n",
    "首先将nums[j] 和 k进行约分\n",
    "nums[i] * (nums[j] / gcd(nums[j], k)) % (k / gcd(nums[j], k)) === 0\n",
    "nums[i] 必须是x = k / gcd(nums[j], k) 的倍数\n",
    "预处理出每个数的因子 \n",
    "哈希表统计每个数的每个因子出现的次数, 对于固定nums[j],cnt[x]即为答案\n",
    "map统计nums[i]各因子出现的次数, 每次加1就变成了当前因子的倍数的个数++\n",
    "\"\"\"\n",
    "MX = 100001\n",
    "div = [[] for _ in range(MX)]\n",
    "for i in range(1, MX): # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        div[j].append(i)\n",
    "class Solution:\n",
    "    def countPairs(self, A: List[int], k: int) -> int:\n",
    "        res, c = 0, Counter()\n",
    "        for x in A:\n",
    "            res += c[k // gcd(x, k)]\n",
    "            for d in div[x]: c[d] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 100010\n",
    "f = [[] for _ in range(M)]\n",
    "for i in range(1, M):\n",
    "    for j in range(i, M, i):\n",
    "        f[j].append(i)\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans += cnt[k//gcd(k, x)]\n",
    "            for v in f[x]:\n",
    "                cnt[v] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):  # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors[v]:\n",
    "                cnt[d] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "from math import gcd\n",
    "\n",
    "# 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0  # 存储满足条件的下标对的数量\n",
    "        cnt = Counter()  # 存储因子出现的次数\n",
    "        \n",
    "        # 遍历数组nums\n",
    "        for v in nums:\n",
    "            # 对于每一个数v，检查有多少先前出现的数与之乘积能被k整除\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            \n",
    "            # 更新因子出现的次数\n",
    "            for d in divisors[v]:\n",
    "                cnt[d] += 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "div = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i, MX, i):\n",
    "        div[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            \n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in div[v]:\n",
    "                # d是v的因子 也就是说d的倍数随着遍历到v 会增加1\n",
    "                cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumberTheoryAllFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil + 100\n",
    "        self.factor = [[1] for _ in range(self.ceil + 1)]\n",
    "        self.get_all_factor()\n",
    "        return\n",
    "\n",
    "    def get_all_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的所有因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            x = 1\n",
    "            while x * i <= self.ceil:\n",
    "                self.factor[x * i].append(i)\n",
    "                x += 1\n",
    "        return\n",
    "    \n",
    "nt = NumberTheoryAllFactor(10**5)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        dct = defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            w = k // math.gcd(num, k)\n",
    "            ans += dct[w]\n",
    "            for w in nt.factor[num]:\n",
    "                dct[w] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx=100001\n",
    "g=defaultdict(list)\n",
    "for i in range(1,mx):\n",
    "    for j in range(i,mx,i):\n",
    "        g[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt=Counter()\n",
    "        res=0\n",
    "        for v in nums:\n",
    "            res+=cnt[k//gcd(k,v)]\n",
    "            for i in g[v]:\n",
    "                cnt[i]+=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/count-equal-and-divisible-pairs-in-an-array/description/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        m = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in m.keys():\n",
    "                m[num] = [i]\n",
    "            else:\n",
    "                m[num].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for num, points in m.items():\n",
    "            for i in range(points.__len__()):\n",
    "                for j in range(i+1, points.__len__()):\n",
    "                    if points[i] * points[j] % k == 0:\n",
    "                        ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        {'nums': [3,1,2,2,2,1,3], 'k': 2},\n",
    "        {'nums': [1,2,3,4], 'k': 1},\n",
    "    ]:\n",
    "        ret = s.countPairs(testcase['nums'], testcase['k'])\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        result=0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and (i*j)%k==0:\n",
    "                    result+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        res = 0\n",
    "        for i in range(l-1):\n",
    "            for j in range(i+1, l):\n",
    "                if nums[i] == nums[j] and (i * j) % k == 0:\n",
    "                    res += 1\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        sum=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i] == nums[j]and (i*j)%k==0:\n",
    "                    sum+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        a=0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and ( i*j ) %k==0:\n",
    "                    a+=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and (i * j) % k == 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0   # 符合要求数对个数\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if (i * j) % k == 0 and nums[i] == nums[j]:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1,len(nums)):\n",
    "                if nums[i] == nums[j] and i*j%k == 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        return sum([nums[i] == nums[j] and (i * j) % k == 0 for i in range(len(nums)) for j in range(i + 1, len(nums))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        counter = {}\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] not in counter.keys():\n",
    "                counter[nums[i]] = [i]\n",
    "            else:\n",
    "                for j in counter[nums[i]]:\n",
    "                    if i*j % k == 0:\n",
    "                        ans += 1\n",
    "                counter[nums[i]].append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i] == nums[j] and i*j%k==0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        s = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for a in range(i+1,n):\n",
    "                if nums[i] == nums[a] and (a*i) % k == 0:\n",
    "                    s+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and (i * j) % k == 0:\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if i*j%k==0 and nums[i] == nums[j]:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        t = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    t += 1\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if (i*j)%k==0 and nums[i]==nums[j]:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        x = 0\n",
    "        zd = dict()\n",
    "        for i, j in enumerate(nums):\n",
    "            if j in zd:\n",
    "                zd[j].append(i)\n",
    "            else:\n",
    "                zd[j] = [i]\n",
    "        for i in zd.values():\n",
    "            n = len(i)\n",
    "            if n > 1:\n",
    "                for j in range(n):\n",
    "                    for z in range(j+1, n):\n",
    "                        if i[j]*i[z]%k == 0:\n",
    "                            x += 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(0, n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0   # 符合要求数对个数\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if (i * j) % k == 0 and nums[i] == nums[j]:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        indicess = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in indicess:\n",
    "                indicess[nums[i]].append(i)\n",
    "            else:\n",
    "                indicess[nums[i]] = [i]\n",
    "        res = 0\n",
    "        for num, indices in indicess.items():\n",
    "            for index0, index1 in combinations(indices, 2):\n",
    "                if (index0 * index1) % k == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if((nums[i] == nums[j]) and ((i * j) % k == 0)):\n",
    "                    count += 1\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        sum=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]==nums[j]and i*j%k==0:\n",
    "                    sum+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans, length = 0, nums.__len__()\n",
    "        for i in range(length):\n",
    "            for j in range(i+1, length):\n",
    "                if nums[i] == nums[j] and i*j % k == 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        res = 0\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length):\n",
    "                if nums[i] == nums[j] and (i * j) % k == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1,len(nums)):\n",
    "                if nums[i] == nums[j] and i*j%k == 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if i < j and nums[i] == nums[j] and (i*j) % k == 0:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if (i*j)%k==0 and nums[i]==nums[j]:\n",
    "                    res+=1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        ans = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            dic[v].append(i)\n",
    "        for j, lst in dic.items():\n",
    "            for a in combinations(lst, 2):\n",
    "                if (a[0] * a[1]) % k == 0:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1,len(nums)):\n",
    "                if nums[i] == nums[j] and i*j%k == 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] == nums[j] and i*j%k == 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        for i,j in enumerate(nums):\n",
    "            if j not in dic.keys():\n",
    "                dic[j] = [i]\n",
    "            else:\n",
    "                dic[j].append(i)\n",
    "        for j in dic.values():\n",
    "            if len(j)>1:\n",
    "                for x in range(len(j)):\n",
    "                    for y in range(x+1,len(j)):\n",
    "                        if j[x]*j[y]%k == 0:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        dic = {v:[] for v in nums}\n",
    "        for i , v in enumerate(nums):\n",
    "            dic[v].append(i)\n",
    "        for pack in dic.values():\n",
    "            for i in range(len(pack)-1):\n",
    "                for j in range(i+1,len(pack)):\n",
    "                    if pack[i]*pack[j]%k == 0: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] == nums[j] and i*j % k == 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and (i*j)%k==0:\n",
    "                    ans+=1         \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        return sum(nums[i] == nums[j] and not i * j % k for i in range(len(nums)) for j in range(i + 1, len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt=0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and (i*j)%k==0:\n",
    "                    cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            if v not in dic:\n",
    "                dic[v] = [i]\n",
    "            else:\n",
    "                dic[v].append(i)\n",
    "        print(dic)\n",
    "        for lst in dic.values():\n",
    "            n = len(lst)\n",
    "            if n > 1:\n",
    "                for a in range(n):\n",
    "                    for b in range(a + 1, n):\n",
    "                        if (lst[a] * lst[b]) % k == 0:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        idx_dic = collections.defaultdict( list )\n",
    "        for idx,n in enumerate( nums ):\n",
    "            idx_dic[n].append( idx)\n",
    "        res = 0\n",
    "        for i in idx_dic.keys():\n",
    "            if len( idx_dic[i] ) < 2:\n",
    "                continue\n",
    "            else:\n",
    "                for tmp_i in range( len( idx_dic[i] ) ):\n",
    "                    for tmp_j in range( tmp_i + 1 , len( idx_dic[i] )  ):\n",
    "                        if (idx_dic[i][tmp_i] * idx_dic[i][tmp_j]) % k == 0:\n",
    "                            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        l = len(nums)\n",
    "        for i in range(l-1):\n",
    "            for j in range(i+1, l):\n",
    "                if nums[i] == nums[j] and (i*j)%k == 0:\n",
    "                    ans += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if nums[i] == nums[j] and i*j % k == 0:\n",
    "                    sum += 1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] == nums[j] and (i*j)%k==0:\n",
    "                    count+=1\n",
    "\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if i*j %k==0 and nums[i]==nums[j]:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import *\n",
    "from re import *\n",
    "from datetime import *\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from bisect import *\n",
    "from copy import *\n",
    "from math import *\n",
    "from random import *\n",
    "from statistics import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from operator import *\n",
    "from io import *\n",
    "from sys import *\n",
    "from json import *\n",
    "from builtins import *\n",
    "from typing import *\n",
    "\n",
    "\"\"\"\n",
    "Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j)\n",
    "where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "\n",
    "Input: nums = [3,1,2,2,2,1,3], k = 2\n",
    "Output: 4\n",
    "Explanation:\n",
    "There are 4 pairs that meet all the requirements:\n",
    "- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.\n",
    "- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.\n",
    "- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.\n",
    "- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.\n",
    "\n",
    "\n",
    "Example 2:\n",
    "\n",
    "\n",
    "Input: nums = [1,2,3,4], k = 1\n",
    "Output: 0\n",
    "Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.\n",
    "\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    " * 1 <= nums.length <= 100\n",
    " * 1 <= nums[i], k <= 100\n",
    "\"\"\"\n",
    "\n",
    "MOD = 1000000007 # 998244353\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        return sum(nums[i] == nums[j] and i * j % k == 0 for i in range(n) for j in range(i + 1, n))\n",
    "\n",
    "# testcases = [\n",
    "#     [],\n",
    "#     # [],\n",
    "# ]\n",
    "\n",
    "# s = Solution()\n",
    "# func_name = dir(s)[-1]\n",
    "# func = getattr(s, func_name)\n",
    "\n",
    "# for args in testcases:\n",
    "#     print(func(*args))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        sum=0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and i *j % k==0:\n",
    "                    sum+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        counts = [[] for _ in range(max(nums)+1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            t = counts[x]\n",
    "            if i % k == 0:\n",
    "                ans += len(t)\n",
    "            else:\n",
    "                for j in t:\n",
    "                    if i * j % k == 0:\n",
    "                        ans += 1\n",
    "            t.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if nums[i] == nums[j] and (i * j) % k == 0:\n",
    "                    ans = ans + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and (i * j) % k == 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, n in enumerate(nums):\n",
    "            d[n].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for l in d.values():\n",
    "            res += sum(i * n % k == 0 for i, n in combinations(l , 2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if (i*j)%k ==0  and nums[i] == nums[j]:\n",
    "                    res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        dic={}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dic:\n",
    "                dic[nums[i]]=[]\n",
    "                dic[nums[i]].append(i)\n",
    "            else:\n",
    "                dic[nums[i]].append(i)\n",
    "        \n",
    "        c=0\n",
    "        for l in dic.values():\n",
    "            print(l)\n",
    "            for i in range(len(l)-1):\n",
    "                for j in range(i+1,len(l)):\n",
    "                    if l[i]*l[j]%k==0:\n",
    "                        \n",
    "                        c+=1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)-1,i,-1):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] == nums[j] and i * j % k == 0:\n",
    "                    res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j] and (i*j)%k==0:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countPairs(self, nums, k):\n",
    "        n = len(nums)\n",
    "        return len([1 for i, x in enumerate(nums) for j in range(i + 1, n) if x == nums[j] and i * j % k == 0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "            res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = Counter(deliciousness)\n",
    "        temp = 0\n",
    "        maxsum = max(deliciousness)\n",
    "        \n",
    "        maxsum = ceil(log(maxsum*2,2))\n",
    "        ans = 0\n",
    "        for i in hashmap:\n",
    "            for j in range(maxsum+1):\n",
    "                if 2**j-i < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if 2**j-i in hashmap:\n",
    "                        if 2**j-i == i:\n",
    "                            temp += hashmap[i]*(hashmap[i]-1)//2\n",
    "                        else:\n",
    "                            ans += hashmap[i]*hashmap[2**j-i]\n",
    "        return (ans//2+temp)%(10**9+7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "            res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "powerOf2 = set()\n",
    "p = 0\n",
    "while(p <= 21):\n",
    "    powerOf2.add(2**p)\n",
    "    p += 1\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        if(len(deliciousness) <= 1):\n",
    "            return 0\n",
    "        mapping = {}\n",
    "        for d in deliciousness:\n",
    "            if(d not in mapping):\n",
    "                mapping[d] = 1\n",
    "            else:\n",
    "                mapping[d] += 1\n",
    "        # nums = sorted(list(mapping.keys()))\n",
    "        nums = list(mapping.keys())\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]*2 in powerOf2):\n",
    "                result += mapping[nums[i]] * (mapping[nums[i]]-1) // 2 \n",
    "            for p2 in powerOf2:\n",
    "                if(p2 >= nums[i] and nums[i] < p2-nums[i] and p2-nums[i] in mapping):\n",
    "                    result += mapping[nums[i]] * mapping[p2-nums[i]]\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        d=defaultdict(int)\n",
    "        res=0\n",
    "        for n in deliciousness:\n",
    "            for i in range(22):\n",
    "                target=1<<i\n",
    "                if n<=target and target-n in d:\n",
    "                    res+=d[target-n]\n",
    "            d[n]+=1\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        ans=0\n",
    "        mod=10**9+7\n",
    "        counter = collections.Counter()\n",
    "        for d in deliciousness:\n",
    "            for i in range(22):\n",
    "                if (1<<i)-d in counter:\n",
    "                    ans= (ans + counter[(1<<i)-d]) % mod\n",
    "            counter[d] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = {}\n",
    "        temp = 0\n",
    "        maxsum = 0\n",
    "        for i in deliciousness:\n",
    "            if i > maxsum:maxsum = i\n",
    "            if i not in hashmap:\n",
    "                hashmap[i] = 1\n",
    "            else:\n",
    "                hashmap[i] += 1\n",
    "        maxsum = ceil(log(maxsum*2,2))\n",
    "        ans = 0\n",
    "        for i in hashmap:\n",
    "            for j in range(maxsum+1):\n",
    "                if 2**j-i < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if 2**j-i in hashmap:\n",
    "                        if 2**j-i == i:\n",
    "                            temp += hashmap[i]*(hashmap[i]-1)//2\n",
    "                        else:\n",
    "                            ans += hashmap[i]*hashmap[2**j-i]\n",
    "        return (ans//2+temp)%(10**9+7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, ans = 1, 0\n",
    "\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            \n",
    "            while target < i:\n",
    "                target *= 2\n",
    "\n",
    "            # target-i 2的幂 - 一个数(A) = 另一个数(B) 那么统计 A 和 B 出现的次数相乘就是所有可能的组合\n",
    "            ans += count[i] * count[target-i]\n",
    "            if target == i:\n",
    "                ans += count[i] * (count[i] - 1) // 2\n",
    "\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        visited = defaultdict(int)\n",
    "        for d in deliciousness:\n",
    "            x = 1 \n",
    "            for _ in range(32):\n",
    "                if x - d in visited:\n",
    "                    res += visited[x - d] % mod\n",
    "                x = x << 1 \n",
    "            visited[d] += 1\n",
    "        return res % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "        res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for d in deliciousness:\n",
    "            for i in range(22):\n",
    "                ans += cnt[(1 << i) - d]\n",
    "                ans %= kmod\n",
    "            cnt[d] += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        def nextpower(x):\n",
    "            x-=1\n",
    "            x|=x>>1\n",
    "            x|=x>>2\n",
    "            x|=x>>4\n",
    "            x|=x>>8\n",
    "            x|=x>>16\n",
    "            return x+1\n",
    "\n",
    "        mod=10**9+7\n",
    "        targets=[1<<i for i in range(22)]\n",
    "        cnt=Counter(deliciousness)\n",
    "        res=0\n",
    "        for n in cnt:\n",
    "            for target in targets:\n",
    "                if target-n in cnt:\n",
    "                    if 2*n==target: res+=cnt[n]*(cnt[n]-1)\n",
    "                    else: res+=cnt[target-n]*cnt[n]\n",
    "        return (res>>1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        d = {}\n",
    "        res = 0\n",
    "        for de in deliciousness:\n",
    "            for i in range(22):\n",
    "                t = 2**i - de\n",
    "                if t in d:\n",
    "                    res = (res+d[t])%1000000007\n",
    "            if de in d:\n",
    "                d[de] += 1\n",
    "            else:\n",
    "                d[de] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        max_val = max(deliciousness)\n",
    "        max_sum = 2 * max_val\n",
    "\n",
    "        # 计算所有可能的2的幂\n",
    "        powers_of_two = [1 << i for i in range(22)]  # 2^21 is greater than 10^6\n",
    "\n",
    "        count = 0\n",
    "        counter = {}\n",
    "        for val in deliciousness:\n",
    "            for power in powers_of_two:\n",
    "                complement = power - val\n",
    "                if complement in counter:\n",
    "                    count += counter[complement]\n",
    "            counter[val] = counter.get(val, 0) + 1\n",
    "\n",
    "        return count % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        d = Counter(deliciousness)\n",
    "        \n",
    "        # compute power of 2 from 2^0 to 2^21, since deliciousness[i] range is [0, 2^20]\n",
    "        power_of_two = [1]\n",
    "        for _ in range(21):\n",
    "            power_of_two.append(power_of_two[-1] << 1)\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for key in d:\n",
    "            # use binary search to search the index of minimum power of 2 using the current number\n",
    "            start_index = bisect_left(power_of_two, key << 1)\n",
    "            for two_num in power_of_two[start_index:]:\n",
    "                if two_num - key not in d:\n",
    "                    continue\n",
    "                if two_num - key != key:\n",
    "                    # if a != b\n",
    "                    res = (res + d[key] * d[two_num - key]) % 1000000007\n",
    "                elif d[key] > 1:\n",
    "                    # if a == b and d[a] > 1\n",
    "                    res = (res + comb(d[key], 2)) % 1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        res = 0\n",
    "        # 由于每个数只遍历了最接近自己的2的次幂的组合，所以不可能重复;比如说1和3构成4，只在3的时候计算；3和5构成8只在5的时候计算。\n",
    "        for i in count:\n",
    "            if i == 0:\n",
    "                continue\n",
    "            # i的下一个2的幂次\n",
    "            target = self.nextPower(i)\n",
    "            # 如果i能和任意的count中的key够成这个幂次\n",
    "            res += count[i] * count[target - i]\n",
    "            # 如果i自身是一个2的幂次\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "        return res % MOD\n",
    "\n",
    "    def nextPower(self, x: int):\n",
    "        x -= 1\n",
    "        x |= x >> 1\n",
    "        x |= x >> 2\n",
    "        x |= x >> 4\n",
    "        x |= x >> 8\n",
    "        x |= x >> 16\n",
    "        return x + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow = [2**x for x in range(22)]\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        cnt = Counter(deliciousness)\n",
    "        ans = 0\n",
    "        for i in cnt:\n",
    "            for j in pow:\n",
    "                tmp = j-i\n",
    "                if tmp in cnt:\n",
    "                    if tmp == i:\n",
    "                        ans += (cnt[i] * (cnt[i] - 1)) // 2\n",
    "                    elif tmp > i:\n",
    "                        ans += cnt[i] * cnt[tmp]\n",
    "                    ans = ans % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x in deliciousness:\n",
    "            for k in range(41):\n",
    "                rest = (1 << k) - x\n",
    "                ans += cnt[rest]\n",
    "            cnt[x] += 1\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        d[i]+d[j]=2**k,k==0,1,2...22\n",
    "        d[i]=2**k-d[j]\n",
    "        \"\"\"\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        mod=10**9+7\n",
    "        for i,x in enumerate(deliciousness):\n",
    "            for k in range(22):\n",
    "                ans=(ans+cnt[2**k-x])%mod\n",
    "            cnt[x]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        for deliciousnes in deliciousness:\n",
    "            for i in range(0, 22):\n",
    "                if ((2 ** i) - deliciousnes) in dic:\n",
    "                    ans += dic[(2 ** i) - deliciousnes]\n",
    "            dic[deliciousnes] = dic.get(deliciousnes, 0) + 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x in deliciousness:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    ans += hashmap[t]\n",
    "                    if ans >= self.mod:\n",
    "                        ans -= self.mod\n",
    "                i <<= 1\n",
    "            hashmap[x] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x in deliciousness:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    ans += hashmap[t]\n",
    "                    if ans >= self.mod:\n",
    "                        ans -= self.mod\n",
    "                i <<= 1\n",
    "            hashmap[x] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = Counter(deliciousness)\n",
    "        ans = 0\n",
    "        for x in hashmap:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    if t == x:\n",
    "                        ans += (hashmap[x] - 1) * hashmap[x]\n",
    "                    else:\n",
    "                        ans += hashmap[x] * hashmap[t]\n",
    "                i <<= 1\n",
    "        ans >>= 1\n",
    "        return ans % self.mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        d[i]+d[j]=2**k,k==0,1,2...22\n",
    "        d[i]=2**k-d[j]\n",
    "        \"\"\"\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        mod=10**9+7\n",
    "        for i,x in enumerate(deliciousness):\n",
    "            for k in range(22):\n",
    "                ans=(ans+cnt[pow(2,k)-x])%mod\n",
    "            cnt[x]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = Counter(deliciousness)\n",
    "        ans = 0\n",
    "        for x in hashmap:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    if t == x:\n",
    "                        ans += (hashmap[x] - 1) * hashmap[x]\n",
    "                    else:\n",
    "                        ans += hashmap[x] * hashmap[t]\n",
    "                i <<= 1\n",
    "        ans >>= 1\n",
    "        return ans % self.mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x in deliciousness:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    ans += hashmap[t]\n",
    "                    if ans >= self.mod:\n",
    "                        ans -= self.mod\n",
    "                i <<= 1\n",
    "            hashmap[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        # deliciousness.sort()\n",
    "        # # print(deliciousness)\n",
    "        # n = len(deliciousness)\n",
    "        # ans = 0\n",
    "        # mod=10**9+7\n",
    "        # # tmp = 0\n",
    "        # # p = []\n",
    "        # freq_dict={}\n",
    "        # for i in range(n):\n",
    "        #     # p.append(tmp)\n",
    "        #     if i > 0 and deliciousness[i] == deliciousness[i - 1] and deliciousness[i] != 0:\n",
    "        #         tot = deliciousness[i] + deliciousness[i - 1]\n",
    "        #         if tmp>0:\n",
    "        #             if tot&(tot-1)==0:\n",
    "        #                 tmp -=1\n",
    "        #                 ans=(tmp+ans)%mod\n",
    "        #             else:\n",
    "        #                 ans=(tmp+ans)%mod\n",
    "        #         continue\n",
    "        #     if i > 0 and deliciousness[i] == deliciousness[i - 1] and deliciousness[i] == 0:\n",
    "        #         if tmp > 0:\n",
    "        #             ans=(tmp+ans)%mod\n",
    "        #         continue\n",
    "        #     tmp = 0\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         total = deliciousness[i] + deliciousness[j]\n",
    "        #         if total != 0:\n",
    "        #             if (total - 1) & total == 0:\n",
    "        #                 tmp += 1\n",
    "        #     ans=(tmp+ans)%mod\n",
    "        # # print(p[1:])\n",
    "        # return ans%mod\n",
    "        ans=0\n",
    "        mod=10**9+7\n",
    "        freq={}\n",
    "        for x in deliciousness:\n",
    "            for j in range(22):\n",
    "                if freq.get(2**j-x,-1)!=-1:\n",
    "                    ans +=freq[2**j-x]\n",
    "            if freq.get(x,-1)!=-1:\n",
    "                freq[x]+=1\n",
    "            else:freq[x]=1\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        cnts = collections.Counter(deliciousness)\n",
    "        res = 0\n",
    "        for key in cnts:\n",
    "            for i in range(22):\n",
    "                opp = (1 << i) - key\n",
    "\n",
    "                if opp != key:\n",
    "                    if opp in cnts:\n",
    "                        res += cnts[key] * cnts[opp]\n",
    "                        # res %= mod\n",
    "                else:\n",
    "                    res += cnts[key] * (cnts[key] - 1)\n",
    "                    # res %= mod\n",
    "\n",
    "\n",
    "        return (res // 2) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x in deliciousness:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    ans += hashmap[t]\n",
    "                    if ans >= self.mod:\n",
    "                        ans -= self.mod\n",
    "                i <<= 1\n",
    "            hashmap[x] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = Counter(deliciousness)\n",
    "        ans = 0\n",
    "        for x in hashmap:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    if t == x:\n",
    "                        ans += (hashmap[x] - 1) * hashmap[x]\n",
    "                    else:\n",
    "                        ans += hashmap[x] * hashmap[t]\n",
    "                i <<= 1\n",
    "        ans >>= 1\n",
    "        return ans % self.mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        d = Counter(deliciousness)\n",
    "        \n",
    "        # compute power of 2 from 2^0 to 2^21, since deliciousness[i] range is [0, 2^20]\n",
    "        power_of_two = [1]\n",
    "        for _ in range(21):\n",
    "            power_of_two.append(power_of_two[-1] << 1)\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for key in d:\n",
    "            # use binary search to search the index of minimum power of 2 using the current number\n",
    "            start_index = bisect_left(power_of_two, key << 1)\n",
    "            for two_num in power_of_two[start_index:]:\n",
    "                if two_num - key not in d:\n",
    "                    continue\n",
    "                if two_num - key != key:\n",
    "                    # if a != b\n",
    "                    res = (res + d[key] * d[two_num - key]) % 1000000007\n",
    "                elif d[key] > 1:\n",
    "                    # if a == b and d[a] > 1\n",
    "                    res = (res + comb(d[key], 2)) % 1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        ans = 0\n",
    "        m = {}\n",
    "        for c in deliciousness:\n",
    "            for i in range(22):\n",
    "                s = (1<<i)-c\n",
    "                if s in m:\n",
    "                    ans += m[s]\n",
    "                    ans %= MOD\n",
    "            if c in m:\n",
    "                m[c] += 1\n",
    "            else:\n",
    "                m[c] = 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        deliciousness.sort()\n",
    "        counter = Counter()\n",
    "        ret = 0\n",
    "        zero = 0\n",
    "        for x in deliciousness:\n",
    "            if x == 0:\n",
    "                zero += 1\n",
    "                continue\n",
    "            if (x - 1) & x == 0:\n",
    "                k = x\n",
    "                ret += zero\n",
    "            else:\n",
    "                k = (1 << (len(bin(x)) - 2)) - x\n",
    "            ret += counter[k]\n",
    "            counter[x] += 1\n",
    "        return ret % M\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        cnt=collections.Counter()\n",
    "        ans=0\n",
    "        for x in deliciousness:\n",
    "            for i in range(22):\n",
    "                ans+=cnt[(1<<i)-x]\n",
    "            cnt[x]+=1\n",
    "        return ans%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = {}\n",
    "        temp = 0\n",
    "        deliciousness.sort()\n",
    "        for i in deliciousness:\n",
    "            if i not in hashmap:\n",
    "                hashmap[i] = 1\n",
    "            else:\n",
    "                hashmap[i] += 1\n",
    "        ans = 0\n",
    "        for i in hashmap:\n",
    "            for j in range(22):\n",
    "                if 2**j-i < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if 2**j-i in hashmap:\n",
    "                        if 2**j-i == i:\n",
    "                            temp += hashmap[i]*(hashmap[i]-1)//2\n",
    "                        else:\n",
    "                            ans += hashmap[i]*hashmap[2**j-i]\n",
    "        return (ans//2+temp)%(10**9+7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        deliciousness.sort()\n",
    "        for x in deliciousness:\n",
    "            for k in range(41):\n",
    "                rest = (1 << k) - x\n",
    "                ans += cnt[rest]\n",
    "            cnt[x] += 1\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        # 构建哈希表, 列出2的0~21次幂\n",
    "        p = {2**i for i in range(22)}\n",
    "        # 统计各个数出现的次数\n",
    "        m = defaultdict(lambda: 0)\n",
    "\n",
    "        ans = 0\n",
    "        for x in deliciousness:\n",
    "            for mi in p:\n",
    "                if mi - x in m:\n",
    "                    ans += m[mi-x]\n",
    "            m[x] += 1\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        cnt = Counter()\r\n",
    "        res = 0 \r\n",
    "        for x in deliciousness:\r\n",
    "            for j in range(41):\r\n",
    "                if x <= (1 << j):\r\n",
    "                    res = (res + cnt[(1 << j) - x]) % mod\r\n",
    "            cnt[x] += 1\r\n",
    "        return res \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        ans = 0\n",
    "        x = Counter(deliciousness)\n",
    "\n",
    "        for i in x:\n",
    "            st = 0\n",
    "            if i != 0:\n",
    "                st = math.ceil(math.log2(i))\n",
    "            for j in range(st, 22):\n",
    "                req = int(math.pow(2, j) - i)\n",
    "                if req < i:\n",
    "                    continue\n",
    "                if req == i:\n",
    "                    ans += (x[i] * (x[i] - 1)) // 2\n",
    "                else:\n",
    "                    ans += x[i] * x[req]\n",
    "        \n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "\n",
    "        cnt = collections.Counter(deliciousness)\n",
    "        maxv = int(2 * max(cnt.keys()))\n",
    "        good_meals = set()\n",
    "        val = 1\n",
    "        while val <= maxv:\n",
    "            good_meals.add(val)\n",
    "            val *= 2\n",
    "\n",
    "        print(good_meals)\n",
    "        res = 0\n",
    "        for key, val in cnt.items():\n",
    "            for good_meal in good_meals:\n",
    "                if (good_meal - key in cnt) and (good_meal - key != key):\n",
    "                    res += val * cnt[good_meal - key]\n",
    "\n",
    "        res = int(res/2)\n",
    "        # print(res)\n",
    "\n",
    "        for key, val in cnt.items():\n",
    "            for good_meal in good_meals:\n",
    "                if (good_meal - key in cnt) and (good_meal - key == key):\n",
    "                    res +=  int(val * (val -1) /2 )\n",
    "        # print(res)\n",
    "\n",
    "        return res % (10**9 + 7)\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "\n",
    "        cnt = collections.Counter(deliciousness)\n",
    "        maxv = int(2 * max(cnt.keys()))\n",
    "        good_meals = set()\n",
    "        val = 1\n",
    "        while val <= maxv:\n",
    "            good_meals.add(val)\n",
    "            val *= 2\n",
    "\n",
    "        res = 0\n",
    "        for key, val in cnt.items():\n",
    "            for good_meal in good_meals:\n",
    "                if (good_meal - key in cnt) and (good_meal - key != key):\n",
    "                    res += val * cnt[good_meal - key]\n",
    "\n",
    "        res = int(res/2)\n",
    "\n",
    "\n",
    "        for key, val in cnt.items():\n",
    "            for good_meal in good_meals:\n",
    "                if (good_meal - key in cnt) and (good_meal - key == key):\n",
    "                    res +=  int(val * (val -1) /2 )\n",
    "\n",
    "\n",
    "        return res % (10**9 + 7)\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, d: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        res = 0\n",
    "        dic = defaultdict(int)\n",
    "        for num in d:\n",
    "            dic[num]+=1\n",
    "        print(dic)\n",
    "        for k1,v1 in dic.items():\n",
    "            for i in range(22):\n",
    "                k2 = 2**i-k1\n",
    "                if k2 in dic:\n",
    "                    if k1==k2:\n",
    "                        res+=v1*(v1-1)\n",
    "                    else:\n",
    "                        res+=v1*dic[k2] \n",
    "                    continue\n",
    "        return res//2%mod\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # # 枚举 2 的幂（容斥原理）\n",
    "    # O(n∗logC) O(n)\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = Counter(deliciousness)\n",
    "        ans = 0\n",
    "        for x in hashmap:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    if t == x:\n",
    "                        ans += (hashmap[x] - 1) * hashmap[x]\n",
    "                    else:\n",
    "                        ans += hashmap[x] * hashmap[t]\n",
    "\n",
    "                i <<= 1\n",
    "\n",
    "        ans >>= 1\n",
    "        return ans % self.mod\n",
    "\n",
    "\n",
    "\n",
    "    # 枚举 2 的幂（边遍历边统计）\n",
    "    # # O(n∗logC) O(n)\n",
    "    mod = 10 ** 9 + 7\n",
    "    maximum = 1 << 22\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        hashmap = defaultdict(int)\n",
    "        ans = 0\n",
    "        for x in deliciousness:\n",
    "            i = 1\n",
    "            while i < self.maximum:\n",
    "                t = i - x\n",
    "                if t in hashmap:\n",
    "                    ans += hashmap[t]\n",
    "                    if ans >= self.mod:\n",
    "                        ans -= self.mod\n",
    "\n",
    "                i <<= 1\n",
    "\n",
    "            hashmap[x] += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        count = Counter(deliciousness)\n",
    "\n",
    "        target, res = 1, 0\n",
    "        for i in sorted(count):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            while target < i:\n",
    "                target *= 2\n",
    "            res += count[i] * count[target - i]\n",
    "            if i == target:\n",
    "                res += count[i] * (count[i] - 1) // 2\n",
    "            res %= MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "powerOf2 = set()\n",
    "p = 0\n",
    "while(p <= 21):\n",
    "    powerOf2.add(2**p)\n",
    "    p += 1\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        if(len(deliciousness) <= 1):\n",
    "            return 0\n",
    "        mapping = {}\n",
    "        for d in deliciousness:\n",
    "            if(d not in mapping):\n",
    "                mapping[d] = 1\n",
    "            else:\n",
    "                mapping[d] += 1\n",
    "        # nums = sorted(list(mapping.keys()))\n",
    "        nums = list(mapping.keys())\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]*2 in powerOf2):\n",
    "                result += mapping[nums[i]] * (mapping[nums[i]]-1) // 2 \n",
    "            for p2 in powerOf2:\n",
    "                if(p2 >= nums[i] and nums[i] < p2-nums[i] and p2-nums[i] in mapping):\n",
    "                    result += mapping[nums[i]] * mapping[p2-nums[i]]\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        p = [1]\n",
    "        for i in range(1, 22):\n",
    "            p.append(p[-1]*2)\n",
    "        ds = sorted(deliciousness)\n",
    "        i = 0\n",
    "        cnter = collections.Counter()\n",
    "        res = 0\n",
    "        M = 10**9+7\n",
    "        for d in ds:\n",
    "            while p[i] <= d:\n",
    "                i += 1\n",
    "            if i>0 and p[i-1] == d:\n",
    "                res += cnter[0]\n",
    "            res = (res+cnter[p[i]-d])%M\n",
    "            cnter[d] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        counter = Counter(deliciousness)\n",
    "        res = 0\n",
    "        for k, c in counter.copy().items():\n",
    "            for i in range(22):\n",
    "                check = (1 << i) - k\n",
    "                if check == k:\n",
    "                    res += c * (c - 1) // 2\n",
    "                    continue\n",
    "                if check in counter:\n",
    "                    res += c * counter[check]\n",
    "            counter.pop(k)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        # 两个不同餐品的和为2的幂\n",
    "        # 两数之和卷土重来\n",
    "        # 你看20*10^5次方很好看,很不错,现在必须考虑的是每一位的位数与能否组成2的幂了\n",
    "        # 直接暴力就行了,总共就20个数字,你一个一个找不就完事了\n",
    "        count = Counter(deliciousness)\n",
    "        hashmap = {}\n",
    "        res = 0\n",
    "        for i in range(len(deliciousness)):\n",
    "            for j in range(22):\n",
    "                target = 1 << j\n",
    "                if target - deliciousness[i] in hashmap:\n",
    "                    res += hashmap[target - deliciousness[i]]            \n",
    "            if deliciousness[i] in hashmap:\n",
    "                hashmap[deliciousness[i]] += 1 \n",
    "            else:\n",
    "                hashmap[deliciousness[i]] = 1\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        counter = collections.Counter(deliciousness)\n",
    "        deliciousness = list(set(deliciousness))\n",
    "        deliciousness.sort()\n",
    "        n = len(deliciousness)\n",
    "        i = 0\n",
    "        while 2 ** i <= deliciousness[-1] * 2:\n",
    "            l, r = 0, n - 1\n",
    "            while l <= r:\n",
    "                if deliciousness[l] + deliciousness[r] > 2 ** i:\n",
    "                    r -= 1\n",
    "                elif deliciousness[l] + deliciousness[r] < 2 ** i:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    if l == r: ans = (ans + counter[deliciousness[l]] * (counter[deliciousness[l]] - 1) // 2) % mod\n",
    "                    else: ans = (ans + counter[deliciousness[l]] * counter[deliciousness[r]]) % mod\n",
    "                    r -= 1\n",
    "                    l += 1\n",
    "            i += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        counter = collections.Counter(deliciousness)\n",
    "        deliciousness = list(set(deliciousness))\n",
    "        deliciousness.sort()\n",
    "        n = len(deliciousness)\n",
    "        i = 0\n",
    "        while 2 ** i <= deliciousness[-1] * 2:\n",
    "            l, r = 0, n - 1\n",
    "            while l <= r:\n",
    "                if deliciousness[l] + deliciousness[r] > 2 ** i:\n",
    "                    r -= 1\n",
    "                elif deliciousness[l] + deliciousness[r] < 2 ** i:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    if l == r: ans = (ans + counter[deliciousness[l]] * (counter[deliciousness[l]] - 1) // 2) % mod\n",
    "                    else: ans = (ans + counter[deliciousness[l]] * counter[deliciousness[r]]) % mod\n",
    "                    r -= 1\n",
    "                    l += 1\n",
    "            i += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        min_deliciousness = min(deliciousness)\n",
    "        if min_deliciousness <= 0:\n",
    "            min_deliciousness = 0.5\n",
    "        max_deliciousness = max(deliciousness)\n",
    "        count = Counter(deliciousness)\n",
    "        ans = 0\n",
    "        wait_list = [2 ** i for i in\n",
    "                     range(int(math.log(min_deliciousness * 2, 2)), int(math.log(max_deliciousness * 2, 2)) + 1)]\n",
    "        used = set()\n",
    "        for k, v in count.items():\n",
    "            for i in range(len(wait_list)):\n",
    "                if wait_list[i] - k in count:\n",
    "                    if wait_list[i] - k == k and v > 1:\n",
    "                        ans += (1 + v - 1) * (v - 1) // 2\n",
    "                        ans = ans % (10 ** 9 + 7)\n",
    "                    elif wait_list[i] - k == k:\n",
    "                        pass\n",
    "                    else:\n",
    "                        if wait_list[i] - k not in used:\n",
    "                            ans += v * count[wait_list[i] - k]\n",
    "                            ans = ans % (10 ** 9 + 7)\n",
    "            used.add(k)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness) -> int:\n",
    "        d=deliciousness\n",
    "        d.sort()\n",
    "        dp=[0]*(len(d))\n",
    "        dic={d[0]:1}\n",
    "        for i in range(1,len(d)):\n",
    "            count=0\n",
    "            num=d[i]*2\n",
    "            wei=0\n",
    "            while num !=0: \n",
    "                num=num>>1\n",
    "                wei+=1\n",
    "            for j in range(wei-2,wei):\n",
    "                if j<0:\n",
    "                    continue\n",
    "                target=2**(j)-d[i]\n",
    "                if target>=0:\n",
    "                    count+=dic.get(target,0)\n",
    "            dp[i]=dp[i-1]+count\n",
    "            dic[d[i]]=dic.get(d[i],0)+1\n",
    "        return dp[-1]%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        cnts = collections.Counter(deliciousness)\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for key in cnts:\n",
    "            for i in range(22):\n",
    "                opp = (1 << i) - key\n",
    "                if key <= opp:\n",
    "                    searchKey = (key, opp)\n",
    "                else:\n",
    "                    searchKey = (opp, key)\n",
    "\n",
    "                if searchKey in seen:\n",
    "                    continue\n",
    "\n",
    "                if opp != key:\n",
    "                    if opp in cnts:\n",
    "                        res += cnts[key] * cnts[opp]\n",
    "                        res %= mod\n",
    "                        if key <= opp:\n",
    "                            seen.add((key, opp))\n",
    "                        else:\n",
    "                            seen.add((opp, key))\n",
    "                else:\n",
    "                    res += cnts[key] * (cnts[key] - 1) // 2\n",
    "                    res %= mod\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 有多少个2元组，和是2的幂\n",
    "        cnt = Counter(deliciousness)\n",
    "        ans = 0\n",
    "\n",
    "        vis = set()\n",
    "        for k1, v in cnt.items():\n",
    "            for j in range(22):   # 单个元素范围是2^20，两个的和\n",
    "                k2 = 2 ** j - k1\n",
    "                t = (min(k1, k2), max(k1, k2))   \n",
    "                if t in vis: continue\n",
    "                if k1 == k2:\n",
    "                    ans = (ans + v * (v - 1) // 2) % MOD\n",
    "                    vis.add(t)\n",
    "                else:\n",
    "                    if cnt[k2] > 0:\n",
    "                        ans = (ans + v * cnt[k2] % MOD) % MOD\n",
    "                        vis.add(t)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 有多少个2元组，和是2的幂\n",
    "        cnt = Counter(deliciousness)\n",
    "        ans = 0\n",
    "\n",
    "        vis = set()\n",
    "        for k1, v in cnt.items():\n",
    "            for j in range(40):   \n",
    "                k2 = 2 ** j - k1\n",
    "                t = (min(k1, k2), max(k1, k2))   \n",
    "                if t in vis: continue\n",
    "                if k1 == k2:\n",
    "                    ans = (ans + v * (v - 1) // 2) % MOD\n",
    "                    vis.add(t)\n",
    "                else:\n",
    "                    if cnt[k2] > 0:\n",
    "                        ans = (ans + v * cnt[k2] % MOD) % MOD\n",
    "                        vis.add(t)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        # init\n",
    "        counts = [0] * (2 ** 20 + 1)\n",
    "        max_val = deliciousness[0]\n",
    "        for item in deliciousness:\n",
    "            counts[item] += 1\n",
    "            max_val = max(max_val, item)\n",
    "        result = counts[0] * counts[1]\n",
    "        for i in range(1, 21):\n",
    "            target_num = 2 ** i\n",
    "            if max_val * 2 < target_num:\n",
    "                break\n",
    "            for j in range(0, target_num // 2):\n",
    "                result += counts[j] * counts[target_num - j]\n",
    "            result += counts[target_num // 2] * (counts[target_num // 2] - 1) // 2\n",
    "        result += counts[2 ** 20] * (counts[2 ** 20] - 1) // 2\n",
    "        return result % 1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pre=[]\n",
    "i=1\n",
    "while i<=(1<<21):\n",
    "    pre.append(i)\n",
    "    i*=2\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        ans=0\n",
    "        d=defaultdict(int)\n",
    "        for i in deliciousness:\n",
    "            ans+=d[i]\n",
    "            for j in pre:\n",
    "                if j>=i:\n",
    "                    d[j-i]+=1\n",
    "        return ans%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res = [1<<i for i in range(22)]\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        ans = 0\n",
    "        pre = defaultdict(int)\n",
    "        for num in deliciousness:\n",
    "            for p in res:\n",
    "                if p >= num:\n",
    "                    ans += pre[p-num]\n",
    "            pre[num] += 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        deliciousness.sort()\n",
    "        ans = 0\n",
    "        memo = defaultdict(int)\n",
    "        for v in deliciousness:\n",
    "            for p in range(22):\n",
    "                if 2 ** p > 2 * v:\n",
    "                    break\n",
    "                ans += memo[2 ** p - v]\n",
    "            ans %= 10 ** 9 + 7\n",
    "            memo[v] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        max_val = max(deliciousness) * 2\n",
    "        counter = defaultdict(int)\n",
    "        result = 0\n",
    "        for val in deliciousness:\n",
    "            sum_val = 1\n",
    "            while sum_val <= max_val:\n",
    "                res = sum_val - val\n",
    "                result = (result + counter[res]) % (10**9 + 7)\n",
    "                sum_val = sum_val * 2\n",
    "            counter[val] += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        maxVal = max(deliciousness)\n",
    "\n",
    "        maxSum = maxVal * 2\n",
    "        res = 0\n",
    "        map = collections.defaultdict(int)\n",
    "        for i in range(len(deliciousness)):\n",
    "            val = deliciousness[i]\n",
    "            sum_ = 1\n",
    "            while sum_ <= maxSum:\n",
    "                res = (res + map[sum_ - val]) % MOD\n",
    "                sum_ <<= 1\n",
    "            map[val] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        maxVal = max(deliciousness)\n",
    "\n",
    "        maxSum = maxVal * 2\n",
    "        res = 0\n",
    "        map = collections.defaultdict(int)\n",
    "        for i in range(len(deliciousness)):\n",
    "            val = deliciousness[i]\n",
    "            sum_ = 1\n",
    "            while sum_ <= maxSum:\n",
    "                res = (res + map[sum_ - val]) % MOD\n",
    "                sum_ <<= 1\n",
    "            map[val] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def countPairs(self, deliciousness):\n",
    "        \"\"\"\n",
    "        :type deliciousness: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        answer = 0 \n",
    "        mod = 1000000007\n",
    "        freq_map = defaultdict(int)\n",
    "        for x in deliciousness: \n",
    "            for k in range(22): answer += freq_map[2**k - x]\n",
    "            freq_map[x] += 1\n",
    "        return answer % mod\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        # 两个数加起来等于2的幂\n",
    "        # 0 <= deliciousness[i] <= 2^20, 这一个意味着和最多也就2^21\n",
    "        cnt = 0\n",
    "        m = defaultdict(int)\n",
    "        deliciousness.sort()\n",
    "        for x in deliciousness:\n",
    "            for i in range(22):\n",
    "                cnt += m[(1<<i)-x]\n",
    "            m[x] += 1\n",
    "        return cnt % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, deliciousness: List[int]) -> int:\n",
    "        ans = 0\n",
    "        memo = defaultdict(int)\n",
    "        for v in deliciousness:\n",
    "            for p in range(22):\n",
    "                ans += memo[2 ** p - v]\n",
    "            ans %= 10 ** 9 + 7\n",
    "            memo[v] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
